package org.example.Backtracking_algorithm;


import java.util.*;

public class Reschedule_the_itinerary {
    public static LinkedList<String> arrayList = new LinkedList<>();
    public static LinkedList<String> value = new LinkedList<>();
    public static boolean flag = false;
    public static void main(String[] args) {
        //这道题不能用回溯的方法做，不然全部超时
        //重新安排行程

        //给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
        //所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
        //例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
        //假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(Arrays.asList("JFK", "SFO"));
        tickets.add(Arrays.asList("JFK", "ATL"));
        tickets.add(Arrays.asList("SFO", "ATL"));
        tickets.add(Arrays.asList("ATL", "JFK"));
        tickets.add(Arrays.asList("ATL", "SFO"));
        findItinerary2(tickets);
        for (String s : arrayList) {
            System.out.print(s+" ");
        }
    }
    //第二种方法超出时间限制
    public static List<String> findItinerary2(List<List<String>> tickets) {
        //排序
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        boolean[]  used = new boolean[tickets.size()];
        Arrays.fill(used,false);
        value.add("JFK");
        get2((ArrayList)tickets,used);
        return arrayList;
    }
    public static boolean get2(ArrayList<List<String>> tickets,boolean[] used){
        if (value.size() == tickets.size()+1){
            arrayList = new LinkedList<>(value);
            return true;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(value.getLast())){
                value.add(tickets.get(i).get(1));
                used[i] = true;

                if (get2(tickets,used)) return true;
                value.removeLast();
                used[i] = false;

            }

        }
        return false;
    }

    //第一种方法超时
    public static List<String> findItinerary1(List<List<String>> tickets) {
        value.add("JFK");
        get(tickets,"JFK",tickets.size());
        return arrayList;
    }
    public static void get(List<List<String>> tickets,String next,int len){
        if (flag) return;
        if (value.size()==len+1){
            arrayList = new LinkedList<>(value);
            flag = true;
            return;
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < len; i++) {
            int index = getNext(tickets, next,hashSet);
            hashSet.add(index);
            if (index==-1) break;
            LinkedList<List<String>> lists = new LinkedList<>(tickets);
            List<String> removed= lists.remove(index);
            String next_str = removed.get(1);
            value.add(next_str);
            get(lists,next_str,len);
            value.removeLast();
        }
    }
    public static int getNext(List<List<String>> lists,String next,HashSet<Integer> hashSet){
        int index = -1;
        String min_str = "zzzzzzzzzz";
        for (int i = 0; i < lists.size(); i++) {
            if (hashSet.contains(i)) continue;
            if (lists.get(i).get(0).equals(next)){
                String value = lists.get(i).get(1);
                if (min_str.compareTo(value)>0){
                    min_str=value;
                    index = i;
                }
            }
        }
        return index;
    }
    public static void prin(List<List<String>> result){
        for (List<String> list : result) {
            System.out.print("[ ");
            for (String integer : list) {
                System.out.print(integer+" ");
            }
            System.out.print(" ]");
        }
        System.out.println();
    }
}
